
/*
回溯
连接：https://leetcode.cn/problems/generate-parentheses/
题目：22. 括号生成



    3. 解法：
算法思路：
从左往右进⾏递归，在每个位置判断放置左右括号的可能性，若此时放置左括号合理，则放置左括号
继续进⾏递归，右括号同理。
⼀种判断括号是否合法的⽅法：从左往右遍历，左括号的数量始终⼤于等于右括号的数量，并且左括
号的总数量与右括号的总数量相等。因此我们在递归时需要进⾏以下判断：
1. 放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半（若左括号的数量⼤于等于字符
串⻓度的⼀半时继续放置左括号，则左括号的总数量⼀定⼤于右括号的总数量）；
2. 放⼊右括号时需判断此时右括号数量是否⼩于左括号数量。
递归函数设计：void dfs(int step, int left)
参数：step（当前需要填⼊的位置），left（当前状态的字符串中的左括号数量）；
返回值：⽆；
函数作⽤：查找所有合理的括号序列并存储在答案列表中。
递归函数参数设置为当前状态的字符串⻓度以及当前状态的左括号数量，递归流程如下：
1. 递归结束条件：当前状态字符串⻓度与 2*n 相等，记录当前状态并返回；
2. 若此时左括号数量⼩于字符串总⻓度的⼀半，则在当前状态的字符串末尾添加左括号并继续递归，
递归结束撤销添加操作；
3. 若此时右括号数量⼩于左括号数量（右括号数量可以由当前状态的字符串⻓度减去左括号数量求
得），则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作；

*/
class Solution {
public:
    int left,right,num;
    vector<string> ret;
    string path;
    vector<string> generateParenthesis(int n) {
        num = n;
        dfs();
        return ret;
    }
    void dfs()
    {
        if(right == num)
        {
            ret.push_back(path);
            return ;
        }
        if(left<num)
        {
            path.push_back('(');
            left++;
            dfs();
            path.pop_back();
            left--;
        }
        if(right<left)
        {
            path.push_back(')');
            right++;
            dfs();
            path.pop_back();
            right--;
        }
    }
};